package com.data_structure_algorithm.algorithm;

/**
 * @author 何章怀晓 hezhanghuaixiao
 * @version V1.0
 * @desc 8皇后问题
 */
public class EightQueen {

  static int[] arr = new int[8];

  public static void main(String[] args) {
    check(0);

  }

  /**
   * @param n 当前皇后
   * @return boolean
   * @describe
   * @author 何章怀晓 hezhanghuaixiao
   * @date 2022/3/24  10:59
   * @other
   */
  //检测当前皇后和上一个皇后是否冲突
  public static boolean judge(int n) {
    //n和之前的所有皇后作比较，如n==8，说明是最后一个了，和1-7个皇后均做比较
    for (int i = 0; i < n; i++) {
      if (arr[i] == arr[n] || /*判断斜线--> */ Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
        return false;
      }
    }
    return true;
  }

  /**
   * @param n 放置的第N个皇后，索引0开始，如N==8，已经放完了
   * @return void
   * @describe
   * @author 何章怀晓 hezhanghuaixiao
   * @date 2022/3/24  11:09
   * @other
   */
  public static void check(int n) {
    if (n == 8) {
      print();
      return;
    }

    //放置过程中
    for (int i = 0; i < 8; i++) {
      //放到第1列,首次调用是N为0，（0,0）即首行首列
      // 这里会产生回溯，如果judge返回false，那么回退到上一个栈帧，这里的i会变成i++，继续调用judge接口判断冲突
      arr[n] = i;
      //判断冲突
      boolean judge = judge(n);
      if (judge) {
        //每次check都会全部执行一遍for循环，i是位置，n是皇后
        check(n + 1);
      }
    }

  }

  public static void print() {
    for (int item : arr
    ) {
      System.out.print(item);
    }
    System.out.println();
  }
}
